#include "KDTree.h"

//int maxProf;
//int qtdBusc;

int KDTree::constroi(const QVector<Triangulo*>& array, BoundingBox bb)
{

    raiz = divide(new QVector<Triangulo*>(array), bb, 0);

    return 1;
}

const Objeto_3D* KDTree::intecepta(const Raio& r_vis, float* t) const
{

    return busca(r_vis, t, raiz,0);
}

NO* KDTree::divide(QVector<Triangulo*>* vet, BoundingBox bb, int nivel)
{
    NO *no = new NO();
    int val = mediana(*vet, nivel);

    if(vet->size() < MINFILHOS) // tam minimo de no
    {
        no->dir = NULL;
        no->esq = NULL;
        no->corte = NULL;
        no->folha = vet;
        return no;
    }

    QVector<Triangulo*> *vesq = new QVector<Triangulo*>();
    QVector<Triangulo*> *vdir = new QVector<Triangulo*>();

    separa(*vet, vesq, vdir, val, nivel);

    if(vesq->size() == 0 || vdir->size() == 0 || (vesq->size() == vet->size() || vdir->size() == vet->size())) // todos de um lado soh
    {
        delete vesq;
        delete vdir;
        no->dir = NULL;
        no->esq = NULL;
        no->corte = NULL;
        no->folha = vet;
        return no;
    }

    no->folha = NULL;
    delete vet;

    BoundingBox bbe;
    BoundingBox bbd;

    float minX, maxX, minY, maxY, minZ, maxZ;

    minX = bb.getPXMin().getA();
    maxX = bb.getPXMax().getA();
    minY = bb.getPYMin().getA();
    maxY = bb.getPYMax().getA();
    minZ = bb.getPZMin().getA();
    maxZ = bb.getPZMax().getA();

    switch(EIXO(nivel))
    {
        case EIXO_X:
            bbe = BoundingBox(Vetor_3D(minX, minY, minZ), Vetor_3D(val, maxY, maxZ));
            bbd = BoundingBox(Vetor_3D(val, minY, minZ), Vetor_3D(maxX, maxY, maxZ));
            no->corte = new PlanoX(bbe.getPXMax());
            break;
        case EIXO_Y:
            bbe = BoundingBox(Vetor_3D(minX, minY, minZ), Vetor_3D(maxX, val, maxZ));
            bbd = BoundingBox(Vetor_3D(minX, val, minZ), Vetor_3D(maxX, maxY, maxZ));
            no->corte = new PlanoY(bbe.getPYMax());
            break;
        case EIXO_Z:
            bbe = BoundingBox(Vetor_3D(minX, minY, minZ), Vetor_3D(maxX, maxY, val));
            bbd = BoundingBox(Vetor_3D(minX, minY, val), Vetor_3D(maxX, maxY, maxZ));
            no->corte = new PlanoZ(bbe.getPZMax());
    }

    no->bbe = bbe;
    no->bbd = bbd;

    no->esq = divide(vesq, bbe, nivel + 1);
    no->dir = divide(vdir, bbd, nivel + 1);

    return no;

}

float KDTree::mediana(const QVector<Triangulo*>& vet, int nivel)
{
    QVector<float> lista;

    switch(EIXO(nivel))
    {
         case EIXO_X:
            for(int i = 0; i < vet.size(); ++i)
            {
                lista.push_back(vet[i]->getVertice1().X());
                lista.push_back(vet[i]->getVertice2().X());
                lista.push_back(vet[i]->getVertice3().X());
            }
            break;

         case EIXO_Y:
             for(int i = 0; i < vet.size(); ++i)
             {
                lista.push_back(vet[i]->getVertice1().Y());
                lista.push_back(vet[i]->getVertice2().Y());
                lista.push_back(vet[i]->getVertice3().Y());
             }
             break;

         case EIXO_Z:
             for(int i = 0; i < vet.size(); ++i)
             {
                lista.push_back(vet[i]->getVertice1().Z());
                lista.push_back(vet[i]->getVertice2().Z());
                lista.push_back(vet[i]->getVertice3().Z());
             }
     }

     qSort(lista.begin(), lista.end());

     return lista[lista.size() / 2];

}

void KDTree::separa(const QVector<Triangulo*>& vet, QVector<Triangulo*> *vesq, QVector<Triangulo*> *vdir,
                    float val, int nivel)
{
    switch(EIXO(nivel))
    {
         case EIXO_X:
            for(int i=0 ; i<vet.size(); ++i)
            {
                if(vet[i]->getVertice1().X() < val && vet[i]->getVertice2().X() < val && vet[i]->getVertice3().X() < val)
                    vesq->push_back(vet[i]);
                else if (vet[i]->getVertice1().X() >= val && vet[i]->getVertice2().X() >= val && vet[i]->getVertice3().X() >= val)
                    vdir->push_back(vet[i]);
                else
                {
                    vesq->push_back(vet[i]);
                    vdir->push_back(vet[i]);
                }
            }
            break;

         case EIXO_Y:
            for(int i=0 ; i<vet.size(); ++i)
            {
                if(vet[i]->getVertice1().Y() < val && vet[i]->getVertice2().Y() < val && vet[i]->getVertice3().Y() < val)
                    vesq->push_back(vet[i]);
                else if (vet[i]->getVertice1().Y() >= val && vet[i]->getVertice2().Y() >= val && vet[i]->getVertice3().Y() >= val)
                    vdir->push_back(vet[i]);
                else
                {
                    vesq->push_back(vet[i]);
                    vdir->push_back(vet[i]);
                }
            }
            break;

         case EIXO_Z:
            for(int i=0 ; i<vet.size(); ++i)
            {
                if(vet[i]->getVertice1().Z() < val && vet[i]->getVertice2().Z() < val && vet[i]->getVertice3().Z() < val)
                    vesq->push_back(vet[i]);
                else if (vet[i]->getVertice1().Z() >= val && vet[i]->getVertice2().Z() >= val && vet[i]->getVertice3().Z() >= val)
                    vdir->push_back(vet[i]);
                else
                {
                    vesq->push_back(vet[i]);
                    vdir->push_back(vet[i]);
                }
            }
    }
}

const Objeto_3D* KDTree::buscaLinear(const Raio& r_vis, float* ret, const QVector<Triangulo*>& vet) const
{
    float t = -1,t_menor = -1;
    const Objeto_3D* tri = NULL;
    const Objeto_3D* tri_final = NULL;

    for(int i = 0; i < vet.size(); ++i)
    {
        tri = vet[i]->Intercepta( r_vis, &t );
        if(t>0 && (t < t_menor || tri_final == NULL))
        {
            t_menor = t;
            tri_final = tri;
        }
    }

    *ret = t_menor;
    return tri_final;
}

const Objeto_3D* KDTree::busca(const Raio& r_vis, float* t, NO* no, int nivel) const
{
    const Objeto_3D *ret;
    float tmp;
    float tbbe, tbbd;

    if(no->corte == NULL)
        return buscaLinear(r_vis, t, *(no->folha));

    no->bbe.Intercepta(r_vis, &tbbe);
    no->bbd.Intercepta(r_vis, &tbbd);
    no->corte->Intercepta(r_vis, &tmp);

    if(tmp > 0.0)
    {
        if(tbbe < tbbd)
        {
            ret = busca(r_vis, t, no->esq, nivel+1);
            if(ret == NULL)
                return busca(r_vis, t, no->dir, nivel+1);
        }else
        {
            ret = busca(r_vis, t, no->dir, nivel+1);
            if(ret == NULL)
                return busca(r_vis, t, no->esq, nivel+1);
        }
    }else
    {
        if(tbbe > 0)
            ret = busca(r_vis, t, no->esq, nivel+1);
        else
            ret = busca(r_vis, t, no->dir, nivel+1);
    }

    return ret;
}
